package Stack_Queue;

import java.util.Scanner;
import java.util.Stack;

/*给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

        有效字符串需满足：

        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。
        每个右括号都有一个对应的相同类型的左括号。


        示例 1：
        输入：s = "()"
        输出：true

        示例 2：
        输入：s = "()[]{}"
        输出：true

        示例 3：
        输入：s = "(]"
        输出：false*/
public class lc20 {
    public static void main(String[] args) {
        /*
        * 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。 括号匹配1
        * 已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

        第二种情况，括号没有多余，但是 括号的类型没有匹配上。 括号匹配2
        * 遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

        第三种情况，字符串里右方向的括号多余了，所以不匹配。
        * 遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
        * */
        /*String s="(){}}{";
        System.out.println(isValid(s));*/
        Scanner scanner=new Scanner(System.in);
        int n= scanner.nextInt();
        String s=scanner.next();
        isValid(s);

    }

    public static boolean isValid(String s) {
        if(s.length()==1) return false;
        char[] chars = s.toCharArray();
        if(chars[0]==')'||chars[0]==']'||chars[0]=='}') return false;
        Stack<Character> stack=new Stack<>();
        for (char c:chars) {
            if(c=='(') stack.push(')');
            if(c=='{') stack.push('}');
            if(c=='[') stack.push(']');

            if(c==')'){
                if(stack.empty()||stack.peek()!=')') return false;
                stack.pop();
            }
            if(c=='}'){
                if(stack.empty()||stack.peek()!='}') return false;
                stack.pop();
            }
            if(c==']'){
                if(stack.empty()||stack.peek()!=']') return false;
                stack.pop();
            }
        }
        if(stack.empty()) return true;

        return false;
    }
}
